/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package subgradient;

import ilog.concert.IloException;
import ilog.concert.IloIntVar;
import ilog.concert.IloLQNumExpr;
import ilog.concert.IloLinearNumExpr;
import ilog.cplex.IloCplex;

/**
 *
 * @author Guillaume
 */
public class SubGradientSolver {
    
    boolean isOptimal;
    
    IloCplex cplex;
    Solution solInc;
    static final int MAX_K = 2;    //Number of rounds without evolution of LPi
    static final int MAX_ROUND = 1000;    //Maximum number of rounds to obtain a solution.
    static final double PRECISION = 0.001; //Math.pow(10.0, -1.0);
    
    public SubGradientSolver(){
        this.isOptimal = true;
    }
    
    public Solution solve(DataProblem dat) throws IloException{
        
        Solution solToTest = new Solution(1);
        Solution solInc;
        double[] xPi = new double[dat.getNbItems()];
        double LPi = Double.MAX_VALUE; //Initialisé à cause du probable log d'erreur, mais jamais utilisé à cette valeur.
        double LPiPrec = Double.MAX_VALUE;
        double u;
        int t = 0;
        int k = 0;
        
        //trouver un incumbent rapidement : heuristique greedy :
        solInc = greedyAlg(dat);
        u = solInc.profit(dat);        

        
        while(t< MAX_ROUND){
            
            cplex = new IloCplex();
            cplex.setOut(null);
            IloIntVar x[] = cplex.boolVarArray(dat.getNbItems());

            IloLinearNumExpr sumProfit = cplex.linearNumExpr();
            for (int i = 0; i < x.length; i++) {
                sumProfit.addTerm(dat.getListItems().get(i).getProfit(), x[i]);
            }

            IloLinearNumExpr sumWeight = cplex.linearNumExpr();
            for (int i = 0; i < x.length; i++) {
                sumWeight.addTerm(dat.getListItems().get(i).getWeight(), x[i]);
            }

            cplex.addMaximize(cplex.sum(sumProfit,cplex.prod(u, cplex.diff(dat.getCapSac(),sumWeight))));
            
            if(!cplex.solve()){
                System.err.println("Solve fail (infeseability) :");
                System.err.println("Current Value for Lpi : " + LPi + " and LPiPrec : " +  LPiPrec);
                System.err.println("");
                System.err.println("u = " + u);
                System.err.println("k = " + k);
                System.err.println(solInc);
                System.err.println(solToTest);
                throw new  IloException("No optimal solution found");
            }
            
            for (int i = 0; i < x.length; i++) {
                xPi[i] = cplex.getValue(x[i]);
            }
            
            LPi = cplex.getObjValue();
            
            cplex.end();
            
            
            solToTest = new Solution(xPi);
            
            if(solToTest.weight(dat) <= dat.getCapSac()){
                if(solToTest.profit(dat) > solInc.profit(dat)){
                    solInc = new Solution(solToTest);
                }
                
                if( u * (dat.getCapSac() - solToTest.weight(dat)) == 0.0 ){
                    return solToTest;
                }
            }
            
            //Si on n'a toujours pas amélioré theta(u)
            if(Math.abs(LPi - LPiPrec) < PRECISION){
                if(k==MAX_K){
                    return solInc;
                }else{
                    k++;
                }
                
            }else{    
                k=0;
            }
            
            LPiPrec = LPi;
            double alpha = 2.0 * (double) Math.random();   
            double subGrad = dat.getCapSac() - solToTest.weight(dat);
                
            u = Math.abs( u + (alpha * (solInc.profit(dat) - LPi) / subGrad));
            
            t++;
        }
        
        isOptimal = false;
        
        System.err.println("Current Value for Lpi : " + LPi);
        System.err.println("");
        System.err.println("u = " + u);
        System.err.println("k = " + k);
        System.err.println("solInc = " + solInc);
        System.err.println("solToTest = " + solToTest);
        //throw new UnsupportedOperationException("No solution optimal found after MAX_ROUND iterations");
        return solInc;
    }
    
    /**
     * Return false if the solution given by solve() is not optimal.
     * <p>
     * Be careful : it's possible that this method return true and that the solution
     * given by solve() isn't optimal. But, if this method return false, the solution
     * isn't optimal. This is because of constant PRECISION, if it isn't smaller enough,
     * solve() could return a solution that is not optimal.
     * 
     * @return false if the solution is not optimal. 
     */
    public boolean isOptimal(){
        return isOptimal;
    }
    
    private Solution greedyAlg(DataProblem dat){
        
        double[] x = new double[dat.getNbItems()];
        double currCap = dat.getCapSac();
        
        for (int i = 0; i < dat.getListItems().size(); i++) {
            if(dat.getListItems().get(i).getWeight() <= currCap ){
                x[i]=1;
                currCap -= dat.getListItems().get(i).getWeight();
            }else{
                return new Solution(x);
            }
        }
        
        return new Solution(x);
    }
    
}
